package 题目集.线段树or树状数组.树状数组;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/
 */
public class ch02_右侧比它小的数的个数 {
    /**
     * 暴力思路：
     *      遍历每个数时，在遍历一次右侧的数，找出所有比它小的数的个数
     */
    public List<Integer> countSmaller1(int[] nums) {
        LinkedList<Integer> res = new LinkedList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            int count = 0;
            for (int j = nums.length - 1; j > i; j--) {

                if (nums[j] < nums[i]) {
                    count++;
                }
            }
            res.addFirst(count);
        }
        return res;
    }

    /**
     * 树状数组思路：
     *      我们可以把每个数放入到一个数轴中。
     *      当查询比自己小的数，其实就是对数轴进行区间求和
     *      只要将数按从右往左插入到数轴中，数轴中比自己小的数，就是右侧所有比自己小的数。
     *      我们可以用树状数组维护这个数轴。
     *      但由于本题存在负数，所以需要先进行离散化
     */
    int[] tree;

    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> res = new LinkedList<>();
        aggre(nums);
        tree = new int[nums.length + 1];
        for (int i = nums.length - 1; i >= 0; i--) {
            int cnt = query(nums[i] - 1);
            res.addFirst(cnt);
            add(nums[i], 1);
        }
        return res;
    }

    public void add(int i, int v) {
        while (i < tree.length) {
            tree[i] += v;
            i += i & -i;
        }
    }

    public int query(int i) {
        int res = 0;
        while (i > 0) {
            res += tree[i];
            i -= i & -i;
        }
        return res;
    }

    public static void aggre(int[] arr) {
        int[] sort = arr.clone();
        Arrays.sort(sort);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = rank(sort, arr[i]);
        }
    }

    public static int rank(int[] sort, int v) {
        int l = 0, r = sort.length - 1;
        while (l <= r) {
            int m = l + r >> 1;
            if (sort[m] < v) {  //找到第一个小于
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        if (l < sort.length && sort[l] <= v) {
            return l + 1;
        }
        return r + 1;
    }

    @Test
    public void test() {
//        int[] nums = {5, 2, 6, 1};
        int[] nums = {-1, -1};
        System.out.println(countSmaller(nums));
    }
}
